package com.shujujiegou.链表.有序链表;

/**
 * 　   前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，
 *      这称为有序链表。
 *
 * 　　在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。
 *     有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），
 *     另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。
 */
public class OrderLinkedList {
    private Node head;

    public class Node{
        private Integer data;
        private Node next;

        public Node(Integer data) {
            this.data = data;
        }
    }

    public OrderLinkedList() {
        this.head = null;
    }

    //插入节点，并按照从小到大的顺序排列
    public void insert(int data) {
        Node node = new Node(data);
        if(isEmpty()) {
            this.head = node;
        } else {
            Node current = this.head;
            Node previous = this.head;
            while (null != current && data > current.data) {
                previous = current;
                current = current.next;
            }

            if(previous.equals(current)) {
                node.next = this.head;
                this.head = node;
            } else {
                node.next = current;
                previous.next = node;
            }
        }
    }

    //删除头节点
    public void deleteHead() {
        if(isEmpty()) {
            return;
        } else {
            this.head = this.head.next;
        }
    }

    public void display() {
        if(isEmpty()) {
            return;
        } else {
            Node current = this.head;
            while(current != null) {
                System.out.print(current.data + "<<");
                current = current.next;
            }
        }
    }

    // 链表是否为空
    public Boolean isEmpty() {
        return this.head == null ? true : false;
    }

    public static void main(String[] args) {
        OrderLinkedList linkedList = new OrderLinkedList();
        linkedList.insert(5);
        linkedList.insert(4);
        linkedList.insert(3);
        linkedList.insert(2);
        linkedList.insert(1);
        linkedList.insert(6);
        linkedList.insert(7);

        linkedList.display();
    }
}
